An Optimal High Probability Algorithm for the Contextual Bandit Problem

Agnostic Active Learning Without Constraints

Error%2DCorrecting Tournaments.
Abstract. We present a family of adaptive pairwise tournaments that are provably robust against large error fractions when used to determine the largest element in a set. The tournaments use nk pairwise comparisons but have only O(k + log n) depth, where n is the number of players and k is the robustness parameter (for reasonable values of n and k). These tournaments also give a reduction from multiclass to binary classification in machine learning, yielding the best known analysis for the problem. 1


Importance weighted active learning.
We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. 1.
The offset tree for learning with partial labels.

Error%2DCorrecting Tournaments
Abstract. We present a family of adaptive pairwise tournaments that are provably robust against large error fractions when used to determine the largest element in a set. The tournaments use nk pairwise comparisons but have only O(k + log n) depth, where n is the number of players and k is the robustness parameter (for reasonable values of n and k). These tournaments also give a reduction from multiclass to binary classification in machine learning, yielding the best known analysis for the problem. 1
Conditional Probability Tree Estimation Analysis and Algorithms
1.1 Main Results We consider the problem of estimating the conditional probability of a label in time O(log n), where n is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly 10 6 labels. 1
Agnostic active learning.
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A2 (for Agnostic Active), relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A2 achieves an exponential improvement (i.e., requires only O � ln 1 ɛ samples to find an ɛ-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere. 1.
Scalable Topology Discovery and Link State Detection Using Routing Events.

The Offset Tree for Learning with Partial Labels

The Offset Tree for Learning with Partial Labels


Importance Weighted Active Learning
We present a practical and statistically consistent scheme for actively learning binary classifiers under general loss functions. Our algorithm uses importance weighting to correct sampling bias, and by controlling the variance, we are able to give rigorous label complexity bounds for the learning process. 1.

Robust Reductions from Ranking to Classification.
 We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r. This is a large improvement over approaches such as ordering according to regressed scores, which have a regret transform of r ↦ → nr where n is the number of elements.
Evaluation of Optimization Methods for Network Bottleneck Diagnosis.

Agnostic active learning.
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A2 (for Agnostic Active), relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A2 achieves an exponential improvement (i.e., requires only O � ln 1 ɛ samples to find an ɛ-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere. 1.
Agnostic active learning.
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A2 (for Agnostic Active), relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A2 achieves an exponential improvement (i.e., requires only O � ln 1 ɛ samples to find an ɛ-optimal classifier) over the usual sample complexity of supervised learning, for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere. 1.
Cover trees for nearest neighbor.
We present a tree data structure for fast nearest neighbor operations in general npoint metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric’s structure yet maintains all performance properties of a navigating net (Krauthgamer &amp; Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger &amp; Ruhl, 2002), the cover tree data structure can be constructed in O � c 6 n log n � time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O � c 12 log n � time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets. 1.
Cover trees for nearest neighbor.
We present a tree data structure for fast nearest neighbor operations in general npoint metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric’s structure yet maintains all performance properties of a navigating net (Krauthgamer &amp; Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger &amp; Ruhl, 2002), the cover tree data structure can be constructed in O � c 6 n log n � time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O � c 12 log n � time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets. 1.
Weighted One%2DAgainst%2DAll.
3 TTI-Chicago Abstract. A reduction converts a solver for one task into a solver for another task. We introduce a notion of reduction and analyze reductions between different classification tasks. 1 Introduction There are many natural supervised learning tasks; even classification comes in a variety of different forms (binary, multiclass, cost-sensitive, importance weighted, etc.) There are two approaches that one can take: The first is to analyze all tasks independently and devise algorithms for each. The other approach is to use reductions to convert new, unexplored tasks to tasks that have been thoroughly analyzed, automatically transferring existing theory and algorithms from well-understood domains into new domains. We investigate the latter approach for classification problems. Reductions can be a powerful tool with a number of desirable properties: 1. They show how similar different tasks are. If two tasks are reducible to one
Weighted One%2DAgainst%2DAll.
3 TTI-Chicago Abstract. A reduction converts a solver for one task into a solver for another task. We introduce a notion of reduction and analyze reductions between different classification tasks. 1 Introduction There are many natural supervised learning tasks; even classification comes in a variety of different forms (binary, multiclass, cost-sensitive, importance weighted, etc.) There are two approaches that one can take: The first is to analyze all tasks independently and devise algorithms for each. The other approach is to use reductions to convert new, unexplored tasks to tasks that have been thoroughly analyzed, automatically transferring existing theory and algorithms from well-understood domains into new domains. We investigate the latter approach for classification problems. Reductions can be a powerful tool with a number of desirable properties: 1. They show how similar different tasks are. If two tasks are reducible to one
Sensitive Error Correcting Output Codes.

Error limiting reductions between classification tasks.
We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ɛ then the cost-sensitive classifier has cost at most 2ɛ times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning. 1
Test%2Dbased diagnosis tree and matrix representations.
A common problem encountered in many application scenarios is how to represent some prior knowledge about a system in order to determine its true state as efficiently as possible. The information is typically in the form of tests, or questions about the system. Each test can potentially reduce our uncertainty about the system’s state. The problem is to represent the information capturing the dependence between tests, their outcomes, and possible states in an efficiently navigable way to aid diagnosis. The most common such representation is a flowchart with leaf nodes corresponding to possible states, and non-leaf nodes corresponding to tests about the state. The problem with flowcharts is that they are notoriously difficult to maintain. Additional knowledge often has to be manually integrated as the system changes, making it impossible to keep track of all possible decision paths, let alone optimize the flow to maximize performance. We propose an efficient method for optimizing an existing flowchart based on a conversion to an auxiliary matrix representation. The main goal of the paper is show a synergy between the two representations in the hope that this will help practitioners choose a better strategy for their applications. We show that such a conversion suggests ways to improve both representations – ways that were not envisioned when using each representation alone. Finally, we show that the two representations are informationally equivalent in the sense that one can be transformed into the other so that if both are used as black-boxes, one would not be able to tell them apart, regardless of which state the system is in.
Statictical Models for Unequally Spaced Time Series.

Efficient Test Selection in Active Diagnosis via Entropy Approximation.
We consider the problem of diagnosing faults in a system represented by a Bayesian network, where diagnosis corresponds to recovering the most likely state of unobserved nodes given the outcomes of tests (observed nodes). Finding an optimal subset of tests in this setting is intractable in general. We show that it is difficult even to compute the next most-informative test using greedy test selection, as it involves several entropy terms whose exact computation is intractable. We propose an approximate approach that utilizes the loopy belief propagation infrastructure to simultaneously compute approximations of marginal and conditional entropies on multiple subsets of nodes. We apply our method to fault diagnosis in computer networks, and show the algorithm to be very effective on realistic Internet-like topologies. We also provide theoretical justification for the greedy test selection approach, along with some performance guarantees. 1
The enumerability of P collapses P to NC.
We investigate alternative notions of approximation for problems inside P (deter-ministic polynomial time), and show that even a slightly nontrivial information about a problem may be as hard to obtain as the solution itself. For example, we prove that if one could eliminate even a single possibility for the value of an arithmetic circuit on a given input, then this would imply that the class P has fast (polygarithmic time) parallel solutions. In other words, this would constitute a proof that there are no inherently sequential problems in P, which is quite unlikely. The result is robust with respect to eliminating procedures that are allowed to err (by excluding the correct value) with small probability. We also show that several fundamental linear algebra problems are hard in this sense. It turns out that it is as hard to substantially reduce the number of possible values for the determinant and rank as to compute them exactly. Finally, we show that (in some precise sense) randomness can be nontrivially substituted for nondeterminism in space. Although it is believed that randomness does not give more than a constant factor advantage in space over determinism, it is not even known whether it is no more powerful than nondeterminism. We will show that the latter is true for a restricted version of probabilistic logspace, where the error is potentially larger than what can be achieved by amplification.  
Improving Network Robustness.
An important property of networked systems is their robustness against removal of network nodes, through either random node failure or targeted attack. Although design methods have been proposed for creating, ab initio, a network that has optimal robustness according to a given measure, one is often instead faced with an existing network that cannot feasibly be substantially modified or redesigned, yet whose robustness can be improved by a lesser degree of modification. We present empirical results that show how robustness, as measured either by the size of the largest connected component or by the shortest path length between pairs of nodes, is affected by several different strategies that alter the network by rewiring a fraction of the edges or by adding new edges. We find that a modest alteration of an initially ‘scale-free ’ network can usefully improve robustness against attack, particularly when the fraction of attacked nodes is small, and we identify modification schemes that are most effective for this purpose.
The Enumerability of P Collapses P to NC.
We investigate alternative notions of approximation for problems inside P (deter-ministic polynomial time), and show that even a slightly nontrivial information about a problem may be as hard to obtain as the solution itself. For example, we prove that if one could eliminate even a single possibility for the value of an arithmetic circuit on a given input, then this would imply that the class P has fast (polygarithmic time) parallel solutions. In other words, this would constitute a proof that there are no inherently sequential problems in P, which is quite unlikely. The result is robust with respect to eliminating procedures that are allowed to err (by excluding the correct value) with small probability. We also show that several fundamental linear algebra problems are hard in this sense. It turns out that it is as hard to substantially reduce the number of possible values for the determinant and rank as to compute them exactly. Finally, we show that (in some precise sense) randomness can be nontrivially substituted for nondeterminism in space. Although it is believed that randomness does not give more than a constant factor advantage in space over determinism, it is not even known whether it is no more powerful than nondeterminism. We will show that the latter is true for a restricted version of probabilistic logspace, where the error is potentially larger than what can be achieved by amplification.  
Reductions Between Classification Tasks
We introduce a reduction-based model for analyzing supervised learning tasks. We use this model to devise a new reduction from multi-class cost-sensitive classification to binary classification with the following guarantee: If the learned binary classifier has error rate at most ɛ then the cost-sensitive classifier has cost at most 2ɛ times the expected sum of costs of all possible lables. Since cost-sensitive classification can embed any bounded loss finite choice supervised learning task, this result shows that any such task can be solved using a binary classification oracle. Finally, we present experimental results showing that our new reduction outperforms existing algorithms for multi-class cost-sensitive learning. 1
On the Enumerability of the Determinant and the Rank.%2
We investigate the complexity of enumerative approximation of two elementary problems in  linear algebra, computing the rank and the determinant of a matrix. In particular, we show that  if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers,  one of which is guaranteed to be the rank of the matrix, then it can be determined in AC    (with  oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the  enumerator is an FL function, then the problem of computing the rank is in FL. The result holds  for matrices over any commutative ring whose size grows at most polynomially with the size of  the matrix. The existence of such an enumerator also implies a slightly stronger collapse of the  exact counting logspace hierarchy.
Approximability of Probability Distributions.
We consider the question of how well a given distribution can be approximated  with probabilistic graphical models. We introduce a new parameter,   effective treewidth, that captures the degree of approximability as  a tradeoff between the accuracy and the complexity of approximation.
The %28Non%29Enumerability of the Determinant and the Rank.
We investigate alternative notions of approximation for problems inside P (deter-ministic polynomial time), and show that even a slightly nontrivial information about a problem may be as hard to obtain as the solution itself. For example, we prove that if one could eliminate even a single possibility for the value of an arithmetic circuit on a given input, then this would imply that the class P has fast (polygarithmic time) parallel solutions. In other words, this would constitute a proof that there are no inherently sequential problems in P, which is quite unlikely. The result is robust with respect to eliminating procedures that are allowed to err (by excluding the correct value) with small probability. We also show that several fundamental linear algebra problems are hard in this sense. It turns out that it is as hard to substantially reduce the number of possible values for the determinant and rank as to compute them exactly. Finally, we show that (in some precise sense) randomness can be nontrivially substituted for nondeterminism in space. Although it is believed that randomness does not give more than a constant factor advantage in space over determinism, it is not even known whether it is no more powerful than nondeterminism. We will show that the latter is true for a restricted version of probabilistic logspace, where the error is potentially larger than what can be achieved by amplification.  
On the Enumerability of the Determinant and the Rank.%2
We investigate the complexity of enumerative approximation of two elementary problems in  linear algebra, computing the rank and the determinant of a matrix. In particular, we show that  if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers,  one of which is guaranteed to be the rank of the matrix, then it can be determined in AC    (with  oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the  enumerator is an FL function, then the problem of computing the rank is in FL. The result holds  for matrices over any commutative ring whose size grows at most polynomially with the size of  the matrix. The existence of such an enumerator also implies a slightly stronger collapse of the  exact counting logspace hierarchy.


On halving line arrangements.

On the Enumerability of the Determinant and the Rank
We investigate the complexity of enumerative approximation of two elementary problems in  linear algebra, computing the rank and the determinant of a matrix. In particular, we show that  if there exists an enumerator that, given a matrix, outputs a list of constantly many numbers,  one of which is guaranteed to be the rank of the matrix, then it can be determined in AC    (with  oracle access to the enumerator) which of these numbers is the rank. Thus, for example, if the  enumerator is an FL function, then the problem of computing the rank is in FL. The result holds  for matrices over any commutative ring whose size grows at most polynomially with the size of  the matrix. The existence of such an enumerator also implies a slightly stronger collapse of the  exact counting logspace hierarchy.
Fast ordering of large categorical datasets for visualization.

Fast ordering of large categorical datasets for better visualization.

One%2DWay Functions in Worst%2DCase Cryptography Algebraic and Security Properties
We survey recent developments in the study of (worst-case) one-way functions  having strong algebraic and security properties. According to [RS93], this line of  research was initiated in 1984 by Rivest and Sherman who designed two-party secretkey  agreement protocols that use strongly noninvertible, total, associative one-way  functions as their key building blocks. If commutativity is added as an ingredient,  these protocols can be used by more than two parties, as noted by Rabi and Sherman  [RS93] who also developed digital signature protocols that are based on such  enhanced one-way functions.  Until recently, it was an open question whether one-way functions having the  algebraic and security properties that these protocols require could be created from  any given one-way function. Recently, Hemaspaandra and Rothe [HR99] resolved  this open issue in the armative, by showing that one-way functions exist if and  only if strong, total, commutative, associative one-way functions exist...
One%2Dway functions in worst%2Dcase cryptography algebraic and security properties are on the house.

